import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: LIUYANJIAO
 * Date: 2024-10-21
 * Time: 14:22
 */

public class Main {
    class Solution {
        static class TreeNode {
            int val;
            TreeNode left;
            TreeNode right;



            TreeNode(int val) {
                this.val = val;

            }

            public static List<Integer> inorderTraversal(TreeNode root) {
                //非递归实现中序遍历

                Deque<TreeNode> deque=new ArrayDeque<>();
                List<Integer> list=new ArrayList<>();
               while (root!=null||!deque.isEmpty()){
                   while(root!=null){
                       deque.push(root);
                       root=root.left;
                   }
                   TreeNode d=deque.pop();
                   list.add(d.val);
                   root=d.right;

               }
               return list;
            }

            public static List<Integer> preorderTraversal(TreeNode root) {
                Deque<TreeNode> deque=new ArrayDeque<>();
                List<Integer> list=new ArrayList<>();
                while(root!=null||!deque.isEmpty()){
                    while(root!=null){
                        deque.push(root);
                        list.add(root.val);
                        root=root.left;
                    }
                    TreeNode d=deque.pop();
                    root=d.right;
                }
                return list;
            }
            public static int find(int[] inorder,int key){
                for (int i = 0; i < inorder.length; i++) {
                    if(inorder[i]==key){
                        return i;
                    }
                }return -1;
            }
            public static int i=1;
            public static TreeNode buildChild(int lef,int rig,int[] inorder, int[] postorder){
                if(i>postorder.length) return null;
                if(lef>rig) return null;
                int center=find(inorder,postorder[postorder.length-i]);
                i++;
                TreeNode root=new TreeNode(inorder[center]);

                root.right=buildChild(center+1,rig,inorder,postorder);
                root.left=buildChild(lef,center-1,inorder,  postorder);
                return root;

            }

            public static TreeNode  buildTree(int[] inorder, int[] postorder) {

                int lef=0;
                int rig=inorder.length-1;
                TreeNode root=buildChild(lef,rig, inorder,  postorder);
                return root;

            }
            public static void main(String[] args) {
                int[]arr1={-1};
                int[]arr2={-1};
                TreeNode root1=buildTree(arr1,arr2);
                System.out.println(preorderTraversal(root1));
            }
        }
    }
}